package _interview75;

import _object.TreeNode;

/**
 * 437. 路径总和 III
 */
public class No437 {
    private int ans;

    public int pathSum(TreeNode root, int targetSum) {
        bfs(root, targetSum);
        return ans;
    }

    /**
     * 寻找所有可以作为根节点的节点
     */
    private void bfs(TreeNode node, long targetSum) {
        if (node == null) return;
        bfs(node.left, targetSum);
        bfs(node.right, targetSum);
        // 将当前节点作为根节点深度优先遍历
        dfs(node, targetSum);
    }

    /**
     * 以当前节点为根节点向下寻找所有满足条件的路径和
     */
    private void dfs(TreeNode node, long curSum) {
        if (node == null) return;
        if (node.val == curSum) ans++;
        dfs(node.left, curSum - node.val);
        dfs(node.right, curSum - node.val);
    }
}